/*
 * @lc app=leetcode.cn id=167 lang=typescript
 *
 * [167] 两数之和 II - 输入有序数组
 * 
 * 可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。
 * 证明方法如下: 假设最 优解的两个数的位置分别是 l 和 r。
 * 我们假设在左指针在 l 左边的时候，右指针已经移动到了 r; 
 * 此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达 l。
 * 同理，如果我们假设 在右指针在 r 右边的时候，左指针已经移动到了 l;
 * 此时两个指针指向值的和大于给定值，因此 右指针会一直左移直到到达 r。
 * 所以双指针在任何时候都不可能处于 (l,r) 之间，
 * 又因为不满足条件时指针必须移动一个，
 * 所以最终一定会收敛在 l 和 r
 */

// @lc code=start
function twoSum(numbers: number[], target: number): number[] {
    let l = 0, r = numbers.length - 1
    while (l < r) {
        const sum = numbers[l] + numbers[r]
        if (sum == target) break;
        if (sum < target) l ++;
        else r --;
    }
    return [l+1, r+1]
};
// @lc code=end

